#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

import time
from matrix_tools import matrix_power, multiply_1


def time_span(func):
    def wrapper(self, *args, **kwargs):
        b = time.time()
        result = func(self, *args, **kwargs)
        e = time.time()
        print('called %s span %s' %(func.__name__, e-b) )
        return result

    return wrapper

class FibMatrix:

    def _init_value(self, a1, a2, mat):
        self.keys = [[a1], [a2]]
        self.fib_mat = mat

    @time_span
    def fib_matrix(self, nth, a1=0, a2=1):
        ''' nth==0, return a2,
            nth==1, return a1 + a2,
            矩阵法求斐波那契数列
        '''
        mat = [
            [0, 1],     # 0*a1 + 1*a2 = new_a1 [ (0, 1) ]
            [1, 1],     # 1*a1 + 1*a2 = new_a2 [ (1, 1) ]
        ]
        self._init_value(a1, a2, mat)
        power_matrix = matrix_power(self.fib_mat, nth)
        ends_a1_a2 = multiply_1(power_matrix, self.keys)
        return ends_a1_a2[0][0]

    @time_span
    def fib_normal(self, nth, a1=0, a2=1):
        ''' 常规做法'''
        if nth == 0:
            return a1
        if nth == 1:
            return a2

        for i in range(nth):
            a1, a2 = a2, a1 + a2

        return a1

    def fib_inverse_normal(self, nth, a1, a2):
        '''

        '''

    def fib_inverse_matrix(self, nth, a1, a2):
        '''
            new_a1 = 0*a1 + 1*a2
            new_a2 = 1*a1 + 1*a2

            a1 = new_a2 - new_a1 = [-1, 1] [new_a1]
            a2 = new_a1          = [ 1, 0] [new_a2]
        '''
        # 上面矩阵的逆矩阵
        mat = [
            [-1, 1],
            [ 1, 0],
        ]
        self._init_value(a1, a2, mat)
        power_matrix = matrix_power(self.fib_mat, nth)
        ends_a1_a2 = multiply_1(power_matrix, self.keys)
        return ends_a1_a2[0][0]


def main():
    print("start main")
    f = FibMatrix()

    nth = 55000      # 2000是一个分界点, 从此开始fib_matrix方法快于常规方法
    # v1 = f.fib_matrix(nth)
    # v2 = f.fib_normal(nth)
    # print(v1)
    # print(v2)

    nth = 100
    v1 = f.fib_matrix(nth)
    v2 = f.fib_matrix(nth+1)

    vb_0 = f.fib_inverse_matrix(nth+10, v1, v2)
    vb_1 = f.fib_inverse_matrix(nth-6, v1, v2)
    print(vb_0, vb_1)

if __name__ == "__main__":
    main()
